package com.acwing.partition6;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AC532货币系统 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int t = Integer.parseInt(s[0]);
        List<int[]> numList = new ArrayList<>(t);
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(reader.readLine().split("\\s+")[0]);
            s = reader.readLine().split("\\s+");
            int[] nums = new int[n];
            for (int j = 0; j < n; j++) nums[j] = Integer.parseInt(s[j]);
            numList.add(nums);
        }
        List<Integer> answer = dynamicProgramming(numList);
        for (int i = 0; i < answer.size(); i++) writer.write(answer.get(i) + "\n");
        writer.flush();
    }

    private static List<Integer> dynamicProgramming(List<int[]> numList) {
        List<Integer> answer = new ArrayList<>(numList.size());
        for (int[] nums : numList) {
            Arrays.sort(nums);
            int ans = 0, maxNum = nums[nums.length - 1];
            int[] dp = new int[maxNum + 1];
            dp[0] = 1;
            for (int i = 0; i < nums.length; i++) {
                //无法凑出来，需要进行选择
                if (dp[nums[i]] == 0) ans++;
                for (int j = nums[i]; j <= maxNum; j++) {
                    dp[j] += dp[j - nums[i]];
                }
            }
            answer.add(ans);
        }
        return answer;
    }

    private static List<Integer> linearAlgebra(List<int[]> numList) {
        List<Integer> answer = new ArrayList<>(numList.size());
        for (int[] nums : numList) {
            Arrays.sort(nums);
            //只需统计所有物品的体积是否能被其他的线性表出
            int maxNum = nums[nums.length - 1], ans = 0;
            boolean[] dp = new boolean[maxNum + 1];
            dp[0] = true;
            for (int i = 0; i < nums.length; i++) {
                //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的；如果没有被筛掉，则把它加入最大无关向量组
                if (dp[nums[i]]) continue;
                ans++;
                //筛掉当前最大无关向量组能线性表示的体积
                for (int j = nums[i]; j <= maxNum; j++) {
                    dp[j] |= dp[j - nums[i]];
                }
            }
            answer.add(ans);
        }
        return answer;
    }
}
